home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group99a.txt / 000109_icon-group-sender _Tue May 4 15:02:32 1999.msg < prev    next >
Internet Message Format  |  2000-09-20  |  3KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id OAA23035
  4.     for icon-group-addresses; Tue, 4 May 1999 14:58:09 -0700 (MST)
  5. Message-Id: <199905042158.OAA23035@baskerville.CS.Arizona.EDU>
  6. Delivered-To: icon-group@cs.arizona.edu
  7. To: icon-group@optima.CS.Arizona.EDU
  8. Date: 4 May 1999 13:45:16 -0500
  9. From: msglass@MCS.COM (Michael Glass)
  10. Subject: Digit Sort Worst Algorithm
  11. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  12. Status: RO
  13.  
  14.    I just read the article on the digit sort problem in April _Icon Analyst_.
  15. I apologize for posting solution #17 sans explanation.  I was having fun
  16. trying to write a DIFFERENT (not BETTER) solution. I knew it was awful and 
  17. should have said something.
  18.  
  19.    The algorithm is O(n^4).  It works (conceptually) like this:
  20.  
  21.      # Let D[1] ... D[n] be an array of digits called by value
  22.      procedure P(D)
  23.         if there exist i,j such that D[i] and D[j] are out of order
  24.            then
  25.                return P(D with the i and j digits swapped)
  26.            else 
  27.                return D
  28.  
  29.    Since finding two digits to swap is O(n^2), and this thing calls
  30. itself up to O(n^2) times, the worst case performance is O(n^4). 
  31.  
  32.    In words, it is imitating something like an exchange or bubble sort.
  33. The difference is that after every swap, the indices START AGAIN FROM THE
  34. BEGINNING looking for new elements to swap.  So finding the NEXT pair of 
  35. elements to swap is O(n^2).
  36.   
  37.    A non-recursive version would look like this:
  38.  
  39.        for j := 2 to n
  40.          for i := 1 to j-1
  41.             if D[i] > D[j] then {
  42.                swap D[i] and D[j] 
  43.                i := 1             #  The recursive call forces
  44.                j := 1             #  the indices to start at the beginning 
  45.             }
  46.  
  47.    Digits are swapped by arithmetic.  Suppose you have 7830 and you want 
  48. to swap the 7 with the the 3.  The difference 7 - 3 = 4, so you can 
  49. subtract 4000 (converting 7000 to 3000) and add 40 (converting 30 to 70): 
  50.  
  51.    7830 - 4000 + 40 = 3870
  52.  
  53. This is accomplished in the usual way of raising 10 to the powers
  54. of digit positions.
  55.  
  56.    Further inefficiency comes from the fact that the sort is performed
  57. on a string of digits and the arithmetic is performed on the number.  Since
  58. the base representation is the number, the number-to-string conversion is
  59. really overdone.
  60.  
  61.    By the way, I thought there was a kind of sick beauty in using
  62. goal-directed evaluation and tail recursion to produce a two line sort.
  63. Probably it comes from having taught the undergraduate algorithms class
  64. a few times.  You start finding beauty in the darndest algorithms, even if
  65. they take the worst performance in the book and square it.
  66.  
  67.    But there was someting about 25 days of compute time that really took
  68. the shine off of it.
  69.  
  70. -- Michael Glass
  71.  
  72.